/*
 * This file (MathParser.java) is protected by the GNU GPL licence (v2). 
 * Please read the license.txt attached for further informations. 
 * 
 */
package org.algoristes.alkwarel.script;

import java.text.DecimalFormat;
import java.util.Hashtable;

import org.algoristes.alkwarel.utils.Log;

/**
 * Parser able to read a mathematical expression. Supports the following
 * operators (from the highest to the lowest in the precedence order) : <br/>
 * 
 * <ul>
 * <li>! (not)</li>
 * <li>* (multiplication)</li>
 * <li>/ (division)</li>
 * <li>% (modulo)</li>
 * <li>+ (addition)</li>
 * <li>- (subtraction)</li>
 * <li>&lt; (less than)</li>
 * <li>&lt;= (less or equal)</li>
 * <li>&gt; (greater than</li>
 * <li>&gt;= (greater or equal)</li>
 * <li>== (equal)</li>
 * <li>!= (not equal)</li>
 * <li>&amp;&amp; (logical and)</li>
 * <li>|| (logical or)</li>
 * </ul>
 * 
 * 
 * 
 * @author Xavier Gouchet
 * 
 */
public class MathParser {

	/** List of known operators **/
	public static final String[] OPERATORS = new String[] { "!=", "==", ">=",
			">", "<=", "<", "+", "-", "%", "/", "*", "!" };

	/** List of known functions **/
	public static final String[] FUNCTIONS = new String[] { "cos", "sin",
			"floor", "ceil", "sqrt", "max", "min", "abs", "rand" };

	private MathNode mRoot;

	private static Hashtable<String, MathNode> mNodes;

	private static final String PREFIX_MATH_NODE = "__math_node__";
	private static final String PREFIX_FUNC_NODE = "__func_node__";

	/**
	 * Default Constructor
	 */
	public MathParser() {
		mRoot = null;
	}

	/**
	 * Parses the given expression then evaluate it.
	 * 
	 * @param input
	 *            the mathematical expression to evaluate
	 * @return the result of the math expression
	 */
	public String compute(String input) {
		String expr = input.toLowerCase();
		expr = expr.replaceAll("true", "1");
		expr = expr.replaceAll("false", "0");

		parse(expr);
		if (mRoot == null)
			return "0";
		// keep only the interesting part of the double value
		return new DecimalFormat().format(mRoot.eval());
	}

	/**
	 * Parses the given expression by building a tree of each math node (ie
	 * operators or values).
	 * 
	 * @param expr
	 *            the mathematical expression to parse
	 */
	public void parse(String expr) {
		mRoot = buildNodes(expr.trim());
		Log.debug(expr.trim());
		// Log.debug(mRoot.toString());
	}

	/**
	 * Builds a tree of nodes from the mathematical expression
	 * 
	 * @param input
	 * @return the root of the built tree
	 */
	public MathNode buildNodes(String input) {
		String sub = extractParenthesisNodes(input);
		int index;
		MathOperator opNode = null;

		// extract lowest operator with child values
		for (String op : OPERATORS) {
			index = sub.indexOf(op);
			if (index != -1) {
				opNode = new MathOperator(op);
				MathNode headNode = buildNodes(sub.substring(0, index));
				MathNode tailNode = buildNodes(sub.substring(index
						+ op.length()));
				opNode.setChildren(new MathNode[] { headNode, tailNode });
				break;
			}
		}

		// if no operator found, either substitute a parenthesed expression, or
		// a leaf value
		if (opNode == null) {
			if (sub.contains(PREFIX_MATH_NODE)) {
				if (getNodes().containsKey(sub.trim()))
					return getNodes().get(sub.trim());
				return new MathNode("???");
			} else if (sub.contains(PREFIX_FUNC_NODE)) {
				if (getNodes().containsKey(sub.trim()))
					return getNodes().get(sub.trim());
				return new MathNode("???");
			} else
				return new MathNode(sub.trim());
		}

		return opNode;
	}

	/**
	 * Finds the first parenthesis block and extract it
	 * 
	 * @param input
	 * @return the substituted string
	 */
	public String extractParenthesisNodes(String input) {
		int parStart, parEnd;
		parStart = input.indexOf('(');
		parEnd = Utils.getMatchingDelimiter(input, parStart, '(', ')');

		if (parStart != -1) {
			if (parEnd != -1) {// found a valid par sequence
				return extractParenthesisNode(input, parStart, parEnd);
			} else {// closing parenthesis not found, let's inform the user
				throw new RuntimeException("Missing closing parenthesis; "
						+ "opening parenthesis found at <"
						+ Utils.getNeighbourHood(input, parStart, 14) + ">");
			}
		}

		return input;
	}

	/**
	 * Extract a parenthesis block
	 * 
	 * @param input
	 * @param start
	 * @param end
	 * @return the substituted string
	 */
	public String extractParenthesisNode(String input, int start, int end) {
		String head, content, tail, key;

		// get what comes before the parenthesis start
		head = input.substring(0, start);

		// get the content of the parenthesis
		content = input.substring(start + 1, end);

		// check if it is a call to a function
		String function = null;
		for (String fun : FUNCTIONS)
			if (head.endsWith(fun)) {
				function = fun;
				break;
			}

		if (function == null) {
			// it's a simple parenthesis, add the content as a simple node
			key = addNewOperator(content);
		} else {
			// ist a function
			head = input.substring(0, start - function.length());
			key = addNewFunction(function, content);
		}

		// parse what comes after and build it
		tail = extractParenthesisNodes(input.substring(end + 1));

		return head + " " + key + " " + tail;
	}

	/**
	 * @return the nodes available for this parser
	 */
	public final Hashtable<String, MathNode> getNodes() {
		if (mNodes == null) {
			mNodes = new Hashtable<String, MathNode>();
		}
		return mNodes;
	}

	/**
	 * Creates a new node from the given input and add it to the list of nodes
	 * 
	 * @param content
	 * @return the key in the node list
	 */
	public String addNewOperator(String content) {
		String key = PREFIX_MATH_NODE + "_" + getNodes().size();
		MathNode node = buildNodes(content);
		getNodes().put(key, node);
		return key;
	}

	/**
	 * Creates a new node from the given inputs and add it to the list of nodes
	 * 
	 * @param function
	 *            the name of the function
	 * 
	 * @param content
	 *            the content listing the parameters (separated by commas)
	 * @return the key in the node list
	 */
	public String addNewFunction(String function, String content) {
		String key = PREFIX_FUNC_NODE + "_" + getNodes().size();
		MathFunction func = new MathFunction(function);

		String[] params = content.split(",");
		MathNode[] nodes = new MathNode[params.length];
		for (int i = 0; i < params.length; i++)
			nodes[i] = buildNodes(params[i]);

		func.setParameters(nodes);
		getNodes().put(key, func);
		return key;
	}
}
